﻿using System;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_111 : BaseProblem
    {
        public override object GetResult()
        {
            const long max = 10;

            var rs = new long[10];

            for (byte d = 0; d<10; d++)
            {
                for (var k = max; k >1; k--)
                {
                    var mx = (long)Math.Pow(10, max-k);
                    mx--;
                    var qrs = new List<long>();
                    for (var val = 0; val <= mx; val++)
                    {
                        var tm = new List<long>();
                        var qs = "";
                        if (k < max)
                            qs = val.ToString();
                        if (qs.IndexOf(d.ToString()) >= 0) continue;
                        while(qs.Length < max-k)
                        {
                            qs = "0" + qs;
                        }
                        FormePrimesRec(ref tm, qs, k, d, 0);
                        if (tm.Count > 0)
                            foreach (var l in tm)
                            {
                                if (!qrs.Contains(l))
                                    qrs.Add(l);
                            }
                    }
                    if (qrs.Count <= 0)
                        continue;
                    rs[d] = MathLogic.GetSumOfInt(qrs);
                    break;
                }
            }

            long res = 0;
            foreach (var r in rs)
            {
                res += r;
            }
            return res;
        }

        private static void FormePrimesRec(ref List<long> result, string current, long count, byte ins, int index)
        {
            if (count < 0) return;
            if (count == 0)
            {
                var tmp = IsProved(current);
                if (tmp > 0)
                    result.Add(tmp);
                return;
            }
            for (var i = index; i <= current.Length; i++)
            {
                var q = current.Insert(i, ins.ToString());
                FormePrimesRec(ref result, q, count-1, ins, i+1);
            }
        }

        private static long IsProved(string val)
        {
            if (string.IsNullOrEmpty(val)) return -1;
            if (val.StartsWith("0")) return -1;
            if (val.EndsWith("0") || val.EndsWith("2") || val.EndsWith("4") || val.EndsWith("5") || val.EndsWith("6") || val.EndsWith("8"))
                return -1;
            var tmp = Convert.ToInt64(val);
            if (MathLogic.IsPrimeNumber(tmp))
                return tmp;
            return -1;
        }

        public override string Problem
        {
            get
            {
                return @"Considering 4-digit primes containing repeated digits it is clear that they cannot all be the same: 1111 is divisible by 11, 2222 is divisible by 22, and so on. But there are nine 4-digit primes containing three ones:

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

We shall say that M(n, d) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(n, d) represents the number of such primes, and S(n, d) represents the sum of these primes.

So M(4, 1) = 3 is the maximum number of repeated digits for a 4-digit prime where one is the repeated digit, there are N(4, 1) = 9 such primes, and the sum of these primes is S(4, 1) = 22275. It turns out that for d = 0, it is only possible to have M(4, 0) = 2 repeated digits, but there are N(4, 0) = 13 such cases.

In the same way we obtain the following results for 4-digit primes.

Digit, d	M(4, d)	N(4, d)	S(4, d)
0	2	13	67061
1	3	9	22275
2	3	1	2221
3	3	12	46214
4	3	2	8888
5	3	1	5557
6	3	1	6661
7	3	9	57863
8	3	1	8887
9	3	7	48073
For d = 0 to 9, the sum of all S(4, d) is 273700.

Find the sum of all S(10, d).";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 612407567715;
            }
        }

    }
}
